//
// Created by francklinson on 2021/8/15 AT 10:33.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    static constexpr int MOD = 1'000'000'007;

    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        vector<vector<int>> direction{{1,  0},
                                      {-1, 0},
                                      {0,  1},
                                      {0,  -1}};
        int outCount = 0;
        vector<vector<int>> dp(m, vector<int>(n));
        // 起始点  有1种方案
        dp[startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; ++i) {
            vector<vector<int>> temp(m, vector<int>(n));
            for (int j = 0; j < m; ++j) {
                for (int k = 0; k < n; ++k) {
                    int count = dp[j][k];
                    // 如果这一位有方案，可以给四周的格子提供方案
                    if (count > 0) {
                        for (int l = 0; l < 4; ++l) {
                            int nR = j + direction[l][0];
                            int nC = k + direction[l][1];
                            if (nR >= 0 and nR < m and nC >= 0 and nC < n) {
                                temp[nR][nC] = (temp[nR][nC] + count) % MOD;
                            } else {
                                outCount = (outCount + count) % MOD;
                            }
                        }
                    }
                }
            }
            dp = temp;
        }
        return outCount;
    }
};


int main() {
    Solution solution;
    cout << solution.findPaths(2, 2, 2, 0, 0) << endl;
    cout << solution.findPaths(1, 3, 3, 0, 1) << endl;
    return 0;
}

